Katakan abjad Σ ialah suatu set terhingga bukan kosong. Unsur-unsur dalam Σ dipanggil simbol atau aksara. Suatu rentetan terhadap Σ ialah sebarang jujukan terhingga bagi aksara-aksara dalam Σ. Sebagai contoh, jika Σ = {0, 1}, maka 0101 ialah satu rentetan terhadap Σ.

Panjang bagi suatu rentetan ialah integer bukan negatif yang mewakili bilangan aksara yang terkandung dalam rentetan itu. Panjang bagi rentetan s {\displaystyle s} ditulis | s | {\displaystyle |s|} .

Rentetan kosong ialah suatu rentetan unik terhadap Σ dengan panjang 0, dan diberi tatatanda ε atau λ.

Set bagi semua rentetan terhadap Σ dengan panjang n {\displaystyle n} ditulis Σn. Sebagai contoh, jika Σ = {0, 1}, maka Σ2 = {00, 01, 10, 11}. Σ0 = {ε} untuk semua abjad Σ.

Set bagi semua rentetan terhadap Σ dengan sebarang panjang ialah tutupan Kleene bagi Σ dan ditulis Σ*. Dalam sebutan Σn,

Σ ∗ = ⋃ n ∈ N Σ n {\displaystyle \Sigma ^{*}=\bigcup _{n\in \mathbb {N} }\Sigma ^{n}}

Sebagai contoh, jika Σ = {0, 1}, maka Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, …}. Sungguhpun Σ* tak terhingga, semua unsur dalam Σ* mempunyai panjang terhingga.

Sebarang set rentetan terhadap Σ, iaitu subset bagi Σ*, dipanggil bahasa formal terhadap Σ. Sebagai contoh, jika Σ = {0, 1}, maka set bagi semua rentetan yang mengandungi bilangan sifar ganjil ({ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, …}) adalah suatu bahasa formal terhadap Σ.

Penjeraitan dan subrentetan

Penjeraitan ialah suatu operasi dedua dalam Σ*. Untuk sebarang dua rentetan s {\displaystyle s} dan t {\displaystyle t} dalam Σ*, penjeraitan s {\displaystyle s} dan t {\displaystyle t} ialah jujukan aksara dalam s {\displaystyle s} dan diikuti dengan jujukan aksara dalam t {\displaystyle t} , dan ditulis s t {\displaystyle st} . Sebagai contoh, jika Σ = {a, b, …, z}, s {\displaystyle s} = la, dan t {\displaystyle t} = gu, maka s t {\displaystyle st} = lagu dan t s {\displaystyle ts} = gula.

Operasi penjeraitan rentetan adalah kalis sekutuan, tetapi tidak kalis tukar tertib. Rentetan kosong bertindak sebagai unsur identiti terhadap penjeraitan. Untuk semua rentetan s {\displaystyle s} , ε s {\displaystyle s} = s {\displaystyle s} ε = s {\displaystyle s} . Oleh itu, Σ* dan penjeraitan membentuk sebuah monoid, iaitu monoid bebas yang dijana oleh Σ.

Suatu rentetan s {\displaystyle s} dipanggil subrentetan atau faktor bagi rentetan t {\displaystyle t} jika wujud rentetan (termasuk rentetan kosong) u {\displaystyle u} dan v {\displaystyle v} sebegitu rupa sehinggakan t = u s v {\displaystyle t=usv} . Sebagai contoh, jalan adalah subrentetan bagi perjalanan, pejalan, dan jalanan.

Penertiban leksikografi

Jika abjad Σ tertertib seluruh, tertib seluruh bagi Σ* yang dipanggil tertib leksikografi boleh ditakrifkan. Oleh kerana Σ adalah terhingga, penertiban rapi bagi Σ sentiasa boleh dilakukan dan begitu juga bagi Σ*. Sebagai contoh, jika Σ = {0, 1} dan 0 < 1, maka penertiban leksikografi bagi Σ* ialah ε < 0 < 00 < 000 < … < 011 < 0110 < … < 01111 < … < 1 < 10 < 100 < … < 101 < … < 111 …